
#include<iostream>
#include<vector>

using namespace std;

int ret = 0;
const int mod = 998244353;
bool is_prime(int n)
{
    if (n < 2)return false;
    for (int i = 2; i <= n; i++)
        if (n % 2 == 0)return false;
    return true;
}

bool check(const vector<int>& path)
{
    for (int i = 0; i < path.size() - 1; i++)
    {
        if (!is_prime(path[i] * path[i + 1]))
            return false;
    }
    return true;
}

void dfs(int n, vector<int>& path, int& ret, vector<bool>& vis)
{
    if (path.size() == n)
    {
        ret += check(path) % mod;
        ret %= mod;
        return;
    }


    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == false)
        {
            vis[i] = true;
            path.push_back(i);
            dfs(n, path, ret, vis);
            vis[i] = false;
            path.pop_back();
        }
    }

}

int main()
{
    int t = 0;
    cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int>path;
        vector<bool>vis(n + 1);
        int ret = 0;
        dfs(n, path, ret, vis);
        cout << ret;
        if (t) cout << "\n";
    }
    return 0;
}
